/*
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

 

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
*/



int candidatesSize_tmp;
int ansSize;
int combineSize;
int *ansColumnSize;

void dfs(int *candidates, int target, int **ans, int *combine, int idx)
{
    if(idx == candidatesSize_tmp)
    {
        return;
    }
    if(target == 0)
    {
        //满足条件，将数组复制如tmp
        int *tmp = malloc(sizeof(int) * combineSize);
        for(int i=0; i < combineSize; i++)
        {
            tmp[i] = combine[i];
        }
        ans[ansSize] = tmp;
        ansColumnSize[ansSize++] = combineSize;
        return;
    }

    //按顺序从左至右依次尝试数组中的每一个数
    dfs(candidates, target, ans, combine, idx+1);

    //选择当前数并减去
    if(target - candidates[idx] >= 0)
    {
        //记录下当前数
        combine[combineSize++] = candidates[idx];
        dfs(candidates, target - candidates[idx], ans, combine, idx);
        //深度遍历后应该将数组下标回退
        combineSize--;
    }
}

int** combinationSum(int *candidates, int candidatesSize, int target, int *returnSize, int ** returnColumnSize)
{
    candidatesSize_tmp = candidatesSize;
    ansSize = combineSize = 0;
    int **ans = malloc(sizeof(int *) * 150);
    ansColumnSize = malloc(sizeof(int) * 1000);

    int combine[1000];
    dfs(candidates, target, ans, combine, 0);
    *returnSize = ansSize;
    *returnColumnSize = ansColumnSize;
    return ans;
}

//快排

void quicksort(int *array, int low, int high)
{
    int i = low;
    int j = high;
    if(i >= j)
    {
        return;
    }

    int temp = array[low];

    while(i != j)
    {
        while(array[j] >= temp && i < j)
        {
            j--;
        }
        while(array[i] <= temp && i < j)
        {
            i++;
        }
        if(i < j)
        {
            swap(&array[i],&array[j]);
        }
    }

    swap(&array[low], &array[i]);
    quicksort(array, low, i-1);
    quicksort(array, i+1,high);
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}